package bintree

//This Package implements Binary Tree Container and Logic

import (
	"fmt"
)

//this is our generic container
type BTNode struct {
	parent, left, right *BTNode
	base *BinTree
	hight int
	Value interface{}
}

type BinTree struct {
	root *BTNode
	size int
	locked bool
	duplicate bool
}

func NewBTree() *BinTree {
	return new(BinTree)
}

func (t *BinTree)ForceLocked() {
	t.locked=true
}

func (t *BinTree)Duplicate(n bool) {
	t.duplicate = n
}

func (t *BinTree)SetRoot(n *BTNode) (bool, error) {
	if t.root!=nil {
		return false, &NotEmptyError{element: t}
	}
	if n.left!=nil || n.right!=nil || n.parent != nil {
		return false, &NotNodeError{node: n}
	}
	t.root = n
	n.base = t
	t.size = t.size + 1
	return true, nil
}

func (t *BinTree)Root() *BTNode {
	return t.root
}

func (t *BinTree)Size() int {
	return t.size
}

func (t *BinTree)String() string {
	s:= fmt.Sprintf("BinTree(%p):%d", t.root, t.size)
	return s
}

func NewBTNode(value interface{}) *BTNode {
	bt := new(BTNode)
	bt.Value = value
	bt.hight = 1
	return bt
}

func (t *BTNode)Left() *BTNode {
	return t.left
}

func (t *BTNode)Right() *BTNode {
	return t.right
}

func (n *BTNode)String() string {
	s:= fmt.Sprintf("BTNode(%p):%v [%d]", n, n.Value, n.hight)
	return s
}

func (n *BTNode)balance() int {
	hleft:=0
	hright:=0
	if n.left!=nil {
		hleft = n.left.hight
	}
	if n.right!=nil {
		hright = n.right.hight
	}
	return hleft-hright
}
func (n *BTNode)InsertLeft(e *BTNode) (bool, error) {
	if n.base!=nil && n.base.locked {
		return false, &LockedError{node: n}
	}
	return n.insertLeft(e)
}

func (n *BTNode)insertLeft(e *BTNode) (bool, error) {
	if n.left != nil {
		return false, &NotEmptyError{element: n}
	}
	if e.left!=nil || e.right!=nil {
		return false, &NotNodeError{node: e}
	}
	n.left = e
	e.parent = n
	for x, h:=e.parent, 2; x!=nil; x,h=x.parent,h+1 {
		if x.hight < h {
			x.hight = h
		}
	}
	if n.base!=nil {
		e.base = n.base
		e.base.size += 1
	}
	return true, nil
}

func (n *BTNode)InsertRight(e *BTNode) (bool, error) {
	if n.base!=nil && n.base.locked {
		return false, &LockedError{node: n}
	}
	return n.insertRight(e)
}

func (n *BTNode)insertRight(e *BTNode) (bool, error) {
	if n.right != nil {
		return false, &NotEmptyError{element: n}
	}
	if e.left!=nil || e.right!=nil {
		return false, &NotNodeError{node: e}
	}
	n.right = e
	e.parent = n
	for x,h:=e.parent,2; x!=nil; x,h=x.parent,h+1 {
		if x.hight < h {
			x.hight = h
		}
	}
	if n.base != nil {
		e.base = n.base
		e.base.size += 1
	}
	return true, nil
}

func (n *BTNode)Walk(f func (*BTNode, interface{}) bool, uData interface{}) bool {
	goOn := true
	if n.right != nil && goOn {
		goOn = n.right.Walk(f, uData)
	}
	if goOn {
		goOn = f(n, uData)
	}
	if n.left != nil && goOn { 
		goOn = n.left.Walk(f, uData)
	}
	return goOn
}

func appendSupport(n *BTNode, uData interface{}) bool {
	x := uData.(*BinTree)
	n.base = x
	x.size += 1
	return true
}

func detachSupport(n *BTNode, uData interface{}) bool {
	x := uData.(*BinTree)
	n.base = nil
	x.size -= 1
	return true
}

func (n *BTNode) AppendLeft(e* BTNode) (bool, error) {
	if n.base!= nil && n.base.locked {
		return false, &LockedError{node: n}
	}
	return n.appendLeft(e)
}

func (n *BTNode) appendLeft(e* BTNode) (bool, error) {
	if n.left != nil {
		return false, &NotEmptyError{element: n}
	}
	n.left = e
	e.parent = n
	if n.base!=nil {
		e.Walk(appendSupport, n.base)
	}
	for x:=e.parent; x!=nil; x=x.parent {
		x.hight += e.hight
	}
	
	return true, nil
}

func (n *BTNode) AppendRight(e* BTNode) (bool, error) {
	if n.base!= nil && n.base.locked {
		return false, &LockedError{node: n}
	}
	return n.appendRight(e)
}

func (n *BTNode) appendRight(e* BTNode) (bool, error) {
	if n.right != nil {
		return false, &NotEmptyError{element: n}
	}
	n.right = e
	e.parent = n
	if n.base!=nil {
		e.Walk(appendSupport, n.base)
	}
	for x:=e.parent; x!=nil; x=x.parent {
		x.hight += e.hight
	}
	return true, nil
}

func (n *BTNode) Detach() bool {
	if n.base!=nil {
		n.Walk(detachSupport, n.base)
	}
	if n.parent.left == n {
		n.parent.left = nil
	} else {
		n.parent.right = nil 
	}
	for x:=n.parent; x!=nil; x= x.parent {
		l, r:= 0,0
		if x.left!= nil {
			l = x.left.hight
		}
		if x.right!=nil {
			r = x.right.hight
		}
		if r < n.hight && l < n.hight {
			n.hight = n.hight
		}
	}
	n.parent = nil
	return true
}

type Comparable interface {
	Less (Comparable) bool
	More (Comparable) bool
	Equal (Comparable) bool
}

func (t *BinTree) InsertSorted(i Comparable) (bool, error) {
	x, y := t.insertSorted(i)
	if x==nil {
		return false, y
	}
	return true, y
}

func (t *BinTree) insertSorted(i Comparable) (*BTNode, error) {
	if t.root == nil {
		t.locked=true
	} else {
		if !t.locked {
			return nil, &NotSearchableError{element:t}
		}
	}
	inserted := false
	e := NewBTNode(i)
	if t.root == nil {
		t.SetRoot(e)
		return e, nil
	}
	n:= t.root
	for !inserted {
		switch {
		case i.Less(n.Value.(Comparable)):
			if n.left == nil {
				n.insertLeft(e)
				inserted= true
			} else {
				n = n.left
			}
		case i.More(n.Value.(Comparable)):
			if n.right == nil {
				n.insertRight(e)
				inserted = true
			} else { 
				n = n.right
			}
		case i.Equal(n.Value.(Comparable)):
			if t.duplicate {
				if n.left == nil {
					n.insertLeft(e)
					inserted= true
				} else {
					n = n.left
				}
			} else {
				return nil, &DuplicateValueError{element:n} //dupicate value
			}
		}
	}
	return e, nil
}

func (t *BinTree)Search (e Comparable) (*BTNode, error) {
	if t.root == nil {
		return nil, &EmptyError{element:t}
	}
	if !t.locked {
		return nil, &NotSearchableError{element:t}
	}
	n := t.root
	for {
		switch {
		case e.Less(n.Value.(Comparable)):
			if n.left == nil {
				return nil, &NotFoundError{element:e}
			} else {
				n = n.left
			}
		case e.More(n.Value.(Comparable)):
			if n.right == nil {
				return nil, &NotFoundError{element:e}
			} else { 
				n = n.right
			}
		case e.Equal(n.Value.(Comparable)):
			return n, nil
		}
	}
	return nil, nil
}

// we need to rewrite this one in more clean way
// 1. detach the node and append new node 
// 2. append direct elements and rebuild hight stuff
// 3. append remaning subtree and rebuild hight stuff

func resetUpperNodeDeep(n *BTNode) bool {
	for iter:=n.parent; iter!=nil; iter = iter.parent {
		hright := 0
		hleft := 0
		if iter.right!=nil {
			hright = iter.right.hight
		}
		if iter.left!=nil {
			hleft = iter.left.hight
		}
		if hright < hleft {
			if iter.hight != hleft + 1 {
				iter.hight = hleft + 1
			}
		} else {
			if iter.hight!=hright+1 {
				iter.hight = hright + 1
			}
		}
	}
	return true
}

func (t *BinTree)Remove (n *BTNode) (bool, error) {
	if t.root == nil {
 		return false, nil
 	}
 	if !t.locked {
		return false, nil
 	}
	if n == nil {
		return false, nil
	}
	if n.left!=nil && n.right!=nil {
		tmp := n.left
		successor := n.right
		if n.parent != nil {
			if n.parent.left == n {
				n.parent.left = successor
			} else {
				n.parent.right = successor
			}
			successor.parent = n.parent
			resetUpperNodeDeep(successor)
		} else {
			t.root = successor
			successor.parent = nil
		}
		//find a place from tmp if needed
		if tmp!=nil {
			var i *BTNode = successor
			for j:= successor.left; j!=nil; j = j.left {
				i = j
			}
			i.left = tmp
			tmp.parent = i 
			resetUpperNodeDeep(tmp)
		}
	} else {
		if n.left!=nil {
			if n.parent != nil {
 				if n.parent.left==n {
					n.parent.left = n.left
					n.left.parent = n.parent
				} else {
					n.parent.right = n.left
					n.right.parent = n.parent
				}
				resetUpperNodeDeep(n.left)
			} else {
				t.root = n.left
				n.left.parent = nil
			}
 		}
 		if n.right!=nil {
			if n.parent != nil {
				if n.parent.left==n {
					n.parent.left = n.right
					n.right.parent = n.parent
				} else {
					n.parent.right = n.right
					n.right.parent = n.parent
				}
				resetUpperNodeDeep(n.right)
			} else {
				t.root = n.right
				n.right.parent = nil
			}
 		}
	}
	return true, nil 
}

func (t *BinTree) InsertAVL(i Comparable) (bool, error) {
	b, x := t.insertSorted(i)
	if b != nil {
		t.balance(b)
		return true , x
	}
	return false, x
}

func (t *BinTree) rotateLeft(x *BTNode) {
	newBase := x.left
	if x.parent!= nil {
		if x.parent.left == x {
			x.parent.left = newBase
		} else {
			x.parent.right = newBase
		}
	} else {
		t.root = newBase 
	}
	newBase.parent = x.parent
	if newBase.right!=nil {
		newBase.right.parent = x
	}
	x.left = newBase.right
	x.parent = newBase
	newBase.right = x
	if x.left!=nil {
		resetUpperNodeDeep(x.left)
	} else {
		if x.right!=nil {
			resetUpperNodeDeep(x.right)
		} else {
			x.hight = 1
			resetUpperNodeDeep(x)
		}
	}
}

func (t *BinTree) rotateRight(x *BTNode) {
	newBase := x.right
	if x.parent!= nil {
		if x.parent.left == x {
			x.parent.left = newBase
		} else {
			x.parent.right = newBase
		}
	} else {
		t.root = newBase 
	}
	newBase.parent = x.parent
	if newBase.left!=nil {
		newBase.left.parent = x
	}
	x.right = newBase.left
	x.parent = newBase
	newBase.left = x
	if x.right!=nil {
		resetUpperNodeDeep(x.right)
	} else {
		if x.left!=nil {
			resetUpperNodeDeep(x.left)
		} else {
			x.hight = 1
			resetUpperNodeDeep(x)
		}		
	}
}

func (t *BinTree) doubleLeft(x *BTNode) {
	support := x.left
	newNode := support.right
	if x.parent!=nil {
		if x.parent.left == x {
			x.parent.left = newNode
		} else {
			x.parent.right = newNode
		}
	} else {
		t.root = newNode
	}
	newNode.parent = x.parent
	if newNode.left!=nil {
		newNode.left.parent = support
	}
	support.right = newNode.left
	if newNode.right!=nil {
		newNode.right.parent = x
	}
	x.left = newNode.right
	x.parent = newNode
	newNode.right = x
	support.parent = newNode
	newNode.left = support
	if support.right == nil {
		if support.left == nil {
			support.hight = 1
		} else {
			support.hight = support.left.hight + 1
		}
	} else {
		if support.left == nil {
			support.hight = support.right.hight +1 
		} else {
			if support.left.hight > support.left.hight {
				support.hight = support.left.hight + 1
			} else {
				support.hight = support.right.hight + 1
			}
		}
	}
	if x.right == nil {
		if x.left == nil {
			x.hight = 1
		} else {
			x.hight = x.left.hight + 1
		}
	} else {
		if x.left == nil {
			x.hight = x.right.hight + 1 
		} else {
			if x.left.hight > x.left.hight {
				x.hight = x.left.hight + 1
			} else {
				x.hight = x.right.hight + 1
			}
		}
	}
	resetUpperNodeDeep(x)
}

func (t *BinTree) doubleRight(x *BTNode) {
	support := x.right
	newNode := support.left
	if x.parent!=nil {
		if x.parent.left == x {
			x.parent.left = newNode
		} else {
			x.parent.right = newNode
		}
	} else {
		t.root = newNode
	}
	newNode.parent = x.parent
	if newNode.left!=nil {
		newNode.left.parent = x
	}
	x.right = newNode.left
	if newNode.right!=nil {
		newNode.right.parent = support
	}
	support.left = newNode.right
	x.parent = newNode
	newNode.left = x
	support.parent = newNode
	newNode.right = support

	if support.right == nil {
		if support.left == nil {
			support.hight = 1
		} else {
			support.hight = support.left.hight + 1
		}
	} else {
		if support.left == nil {
			support.hight = support.right.hight +1 
		} else {
			if support.left.hight > support.left.hight {
				support.hight = support.left.hight + 1
			} else {
				support.hight = support.right.hight + 1
			}
		}
	}
	if x.right == nil {
		if x.left == nil {
			x.hight = 1
		} else {
			x.hight = x.left.hight + 1
		}
	} else {
		if x.left == nil {
			x.hight = x.right.hight + 1 
		} else {
			if x.left.hight > x.left.hight {
				x.hight = x.left.hight + 1
			} else {
				x.hight = x.right.hight + 1
			}
		}
	}
	resetUpperNodeDeep(x)
}

func (t *BinTree) balance(n *BTNode) {
	for x:= n; x!=nil; x= x.parent {
		if x.balance() >= 2 || x.balance() <= -2{
			if x.balance() < 0 {
				if x.right.balance() > 0 {
					t.doubleRight(x)
				} else {
					t.rotateRight(x)
				}
			} else {
				if x.left.balance() < 0 {
					t.doubleLeft(x)
				} else {
					t.rotateLeft(x)
				}
			}
		}
	}
}